﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyAndSort
{
    class MergeSort : ISortStrategy
    {
        public void Sort<T>(IList<T> array,int keyNum =0) where T : IComparable
        {
            MergeSortEnter(array, 0, array.Count-1);
        }

        void MergeSortEnter<T>(IList<T> array , int left,int right) where T :IComparable
        {
            if (left < right)
            {
                int mid = (left + right) / 2;
                MergeSortEnter(array, left, mid);
                MergeSortEnter(array, mid + 1, right);
                Merge(array, left, mid, right);
            }
        }

        private void Merge<T>(IList<T> array,int left,int mid,int right) where T : IComparable
        {
            int i, j, k;
            IList<T> tempArr = new List<T>();
            foreach(T temp in array)   tempArr.Add(temp);
            for( i = left, j = mid + 1, k = i; i <= mid && j <= right; k++)
            {
                if (tempArr[i].CompareTo(tempArr[j]) <= 0)
                    array[k] = tempArr[i++];
                else
                    array[k] = tempArr[j++];
            }
            while (i <= mid) array[k++] = tempArr[i++];
            while (j <= right) array[k++] = tempArr[j++];
        }
    }
}
